#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include"bitree.h"

typedef struct node
{
	bitree_list_t data;//数据域
	struct node *next;//指针域
}linkqueue_node_t,*linkqueue_list_t;

//1.创建一个空的队列
linkqueue_list_t CreateEmptyLinkQueue(){
    linkqueue_node_t* p = (linkqueue_node_t*)malloc(sizeof(linkqueue_node_t));
    if(p == NULL){
        printf("malloc p err\n");
        return NULL;
    }
    p->data = NULL;
    p->next = p;
    return p;
}

//2.入列 data代表入列的数据
int InLinkQueue(linkqueue_node_t *p,bitree_list_t data){
    if(p == NULL){
        return -1;
    }
    linkqueue_node_t*new=(linkqueue_node_t*)malloc(sizeof(linkqueue_node_t));
    if(new == NULL){
        printf("新节点分配失败\n");
        return -1;
    }
    linkqueue_node_t* temp=p;
    while(temp->next != p){
        temp=temp->next;
    }
    new->data=data;
    temp->next=new;
    new->next=p;
}

//4.判断队列是否为空
int IsEmptyLinkQueue(linkqueue_node_t *p){
    if(p == NULL){
        return -1;
    }
    return p == p->next;
}

//3.出列
bitree_list_t OutLinkQueue(linkqueue_list_t p){
    if(p == NULL){
        return NULL;
    }
    if(IsEmptyLinkQueue(p)){
        printf("队空!");
        return NULL;
    }
    linkqueue_node_t* node = p->next;
    bitree_node_t* temp = node->data;
    p->next = node->next;
    free(node);
    return temp;
}

bitree_list_t CreateBitree(int n,int i){//i根节点的编号，n：节点数
    bitree_list_t node=(bitree_list_t)malloc(sizeof(bitree_node_t));
    if(node == NULL){
        printf("malloc node err\n");
        return NULL;
    }
    node->data=i;
    if( 2*i <= n ){
        node->lchild= CreateBitree(n,2*i);
    }else{
        node->lchild=NULL;
    }
    if( (2*i+1) <= n ){
        node->rchild= CreateBitree(n,(2*i+1));
    }else{
        node->rchild=NULL;
    }
    return node;
}

//前序
void PreOrder(const bitree_list_t r){
    if(r == NULL){
        return;
    }
    printf("%d ",r->data);
    if(r->lchild != NULL){
        PreOrder(r->lchild);
    }
    if(r->rchild != NULL){
        PreOrder(r->rchild);
    }
    return;

}

//中序
void InOrder(const bitree_list_t r){
    if(r == NULL){
        return;
    }
    if(r->lchild != NULL){
        InOrder(r->lchild);
    }
    printf("%d ",r->data);
    if(r->rchild != NULL){
        InOrder(r->rchild);
    }
    
}

//后序
void PostOrder(const bitree_list_t r){
    if(r == NULL){
        return;
    }
    if(r->lchild != NULL){
        PostOrder(r->lchild);
    }

    if(r->rchild != NULL){
        PostOrder(r->rchild);
    }
    printf("%d ",r->data);
}

//层次
void unOrder(const bitree_list_t *r){
    if((*r) == NULL){
        return;
    }
    linkqueue_node_t* p=CreateEmptyLinkQueue();
    //根先进队
    InLinkQueue(p,(*r));
    while (!IsEmptyLinkQueue(p)){
        bitree_list_t node = OutLinkQueue(p);
        //将node 进行打印
        printf("%d ", node->data);
        //如果有左孩子
        if (node->lchild != NULL){
            InLinkQueue(p, node->lchild);
        }
        //如果有右孩子
        if (node->rchild != NULL){
            InLinkQueue(p, node->rchild);
        }
    }
    free(p);
    p=NULL;
}

void clear(bitree_list_t *r){
    if((*r) == NULL){
        return;
    }
    
    if((*r)->lchild != NULL){
        clear(&( (*r)->lchild) );
    }

    if((*r)->rchild != NULL){
        clear(&( (*r)->rchild) );
    }
    free((*r));
    (*r)=NULL;
}